在前兩週的課程中，我們探討的對稱加密（AES、ChaCha20）透過 S-Box 替換、P-Box 置換與 XOR 運算，將資料混淆與擴散至極致。然而，進入非對稱加密（Asymmetric Cryptography）的世界後，密碼學的安全根基將從「結構複雜度」轉移至「純粹的抽象數論與數學難題」。
非對稱加密要解決的核心問題是：如何在公開且不安全的通道上，讓雙方進行只有彼此能解密的通訊？
要理解這項偉大的發明，我們需要從最基礎的數學工具開始，理解非對稱密碼學的設計基礎。
數論是研究整數及其性質的數學分支。
在日常程式開發中，我們經常處理字串、日期、金額、資料庫紀錄與網路訊息；而在密碼學中，某些演算法會將資料轉換成整數，再利用整數的數學性質建立加密機制。
例如：
這些演算法並不是單純把數字算得很大，而是利用特定的數學結構，讓正向運算容易執行，某些反向求解問題卻難以在合理時間內完成。
先從最基本的整數概念開始。
假設有一個整數 12，可以被哪些正整數整除？
12 = 1 x 12 = 2 x 6 = 3 x 4
因此，12 的正因數為：
1,2,3,4,6,12
如果一個大於 1 的整數，除了 1 與它本身以外，沒有其他正因數，就稱為質數（Prime Number）。
例如：
2,3,5,7,11,13,17,19,...
質數在 RSA 中扮演重要角色。RSA 金鑰產生時會選擇兩個大質數 p 與 q，再將它們相乘：
n=pq
當 p 與 q 是適當的大質數時，從 p 和 q 計算 n 很容易；但只知道 n，要將它分解回 p 和 q，在使用足夠大且適當產生的參數時，對現有的傳統電腦而言可能非常困難。
這就是 RSA 安全性的重要數學背景之一。
不過要注意，質數本身並不等於安全性。實際安全性還取決於金鑰長度、參數產生方式、填補機制、實作細節，以及攻擊者能使用的計算資源。
兩個整數共同擁有的因數中，最大的那個稱為最大公因數。
例如：
gcd(12,18)=6
因為 12 與 18 的共同因數為 1、2、3、6，其中最大的是 6。
再看另一個例子：
gcd(8,15)=1
當兩個整數的最大公因數是 1 時，我們稱它們互質（Coprime）。
互質的概念在模運算中非常重要。稍後會看到，當整數 a 與模數 n 互質時，a 才具有模 n 的乘法反元素。
而這個性質，正是理解 RSA 私密指數如何建立的重要前置知識。
接下來進入今天最重要的概念：模運算。
模運算可以先用一個生活中的例子理解——時鐘。
一般的整數加法會一直往上增加：
10+5=15
但如果我們使用 12 小時制的時鐘，從 10 點再過 5 小時，結果不是 15 點，而是 3 點。
因為時鐘走到 12 之後，就會重新從 0 開始計算。
這就是模運算的直覺。
在程式設計中，我們常用 % 表示取餘數運算。
例如：
System.out.println(10 % 3); // 1
System.out.println(14 % 5); // 4
System.out.println(17 % 6); // 5
數學上，模運算通常寫成：
a mod n
它表示 a 除以 n 所得到的餘數。
例如：
17 mod 6=5
因為：
17=6x2+5
其中 5 就是餘數。
更一般地，對非負整數 a 與正整數 n，可以寫成：
a=qn+r, 0<= r < n
其中：
在密碼學中，模數通常是演算法參數的一部分。許多運算都會限制在一個有限的數值範圍內，而不是讓結果無限制增長。
假設我們只關心除以 7 的餘數，那麼結果只可能是：
0,1,2,3,4,5,6
無論原始數字多大，最後都能歸類到這七種餘數之一。
例如：
8 mod7=1
15 mod7=1
22 mod7=1
雖然 8、15、22 是不同的數字，但它們除以 7 的餘數相同。
我們可以寫成：
8 ≡ 15 ≡ 22 mod7
這個符號稱為模同餘（Congruence）。
一般而言：
a ≡ b mod n
代表 a 與 b 除以 n 的餘數相同，也等價於 n 可以整除 a-b。
也就是：
n | (a-b)## 前言
在前兩週的課程中，我們探討的對稱加密（AES、ChaCha20）透過 S-Box 替換、P-Box 置換與 XOR 運算，將資料混淆與擴散至極致。然而，進入非對稱加密（Asymmetric Cryptography）的世界後，密碼學的安全根基將從「結構複雜度」轉移至「純粹的抽象數論與數學難題」。
非對稱加密要解決的核心問題是：如何在公開且不安全的通道上，讓雙方進行只有彼此能解密的通訊？
要理解這項偉大的發明，我們需要從最基礎的數學工具開始，理解非對稱密碼學的設計基礎。
數論是研究整數及其性質的數學分支。
在日常程式開發中，我們經常處理字串、日期、金額、資料庫紀錄與網路訊息；而在密碼學中，某些演算法會將資料轉換成整數，再利用整數的數學性質建立加密機制。
例如：
這些演算法並不是單純把數字算得很大，而是利用特定的數學結構，讓正向運算容易執行，某些反向求解問題卻難以在合理時間內完成。
先從最基本的整數概念開始。
假設有一個整數 12，可以被哪些正整數整除？
12 = 1 x 12 = 2 x 6 = 3 x 4
因此，12 的正因數為：
1,2,3,4,6,12
如果一個大於 1 的整數，除了 1 與它本身以外，沒有其他正因數，就稱為質數（Prime Number）。
例如：
2,3,5,7,11,13,17,19,...
質數在 RSA 中扮演重要角色。RSA 金鑰產生時會選擇兩個大質數 p 與 q，再將它們相乘：
n=pq
當 p 與 q 是適當的大質數時，從 p 和 q 計算 n 很容易；但只知道 n，要將它分解回 p 和 q，在使用足夠大且適當產生的參數時，對現有的傳統電腦而言可能非常困難。
這就是 RSA 安全性的重要數學背景之一。
不過要注意，質數本身並不等於安全性。實際安全性還取決於金鑰長度、參數產生方式、填補機制、實作細節，以及攻擊者能使用的計算資源。
兩個整數共同擁有的因數中，最大的那個稱為最大公因數。
例如：
gcd(12,18)=6
因為 12 與 18 的共同因數為 1、2、3、6，其中最大的是 6。
再看另一個例子：
gcd(8,15)=1
當兩個整數的最大公因數是 1 時，我們稱它們互質（Coprime）。
互質的概念在模運算中非常重要。稍後會看到，當整數 a 與模數 n 互質時，a 才具有模 n 的乘法反元素。
而這個性質，正是理解 RSA 私密指數如何建立的重要前置知識。
接下來進入今天最重要的概念：模運算。
模運算可以先用一個生活中的例子理解——時鐘。
一般的整數加法會一直往上增加：
10+5=15
但如果我們使用 12 小時制的時鐘，從 10 點再過 5 小時，結果不是 15 點，而是 3 點。
因為時鐘走到 12 之後，就會重新從 0 開始計算。
這就是模運算的直覺。
在程式設計中，我們常用 % 表示取餘數運算。
例如：
System.out.println(10 % 3); // 1
System.out.println(14 % 5); // 4
System.out.println(17 % 6); // 5
數學上，模運算通常寫成：
a mod n
它表示 a 除以 n 所得到的餘數。
例如：
17 mod 6=5
因為：
17=6x2+5
其中 5 就是餘數。
更一般地，對非負整數 a 與正整數 n，可以寫成：
a=qn+r, 0<= r < n
其中：
在密碼學中，模數通常是演算法參數的一部分。許多運算都會限制在一個有限的數值範圍內，而不是讓結果無限制增長。
假設我們只關心除以 7 的餘數，那麼結果只可能是：
0,1,2,3,4,5,6
無論原始數字多大，最後都能歸類到這七種餘數之一。
例如：
8 mod7=1
15 mod7=1
22 mod7=1
雖然 8、15、22 是不同的數字，但它們除以 7 的餘數相同。
我們可以寫成：
8 ≡15 ≡22 mod7
這個符號稱為模同餘（Congruence）。
一般而言：
a ≡ b mod n
代表 a 與 b 除以 n 的餘數相同，也等價於 n 可以整除 a-b。
也就是：
n\mid(a-b)
這個概念比單純的取餘數更重要，因為密碼學中的許多公式不是只看某一次運算的餘數，而是建立在一整套模同餘關係上。
模運算有一些很好用的規則。只要理解這些規則，就能將大型整數運算簡化成較小的數值。
假設模數為 n，我們可以利用下列性質。
(a+b) mod n = ((a mod n)+(b mod n)) mod n
例如：
(17+23) mod7
=40 mod7
=5
也可以先各自取模：
(3+2) mod7=5
結果相同。
(a-b) mod n = ((a mod n)-(b mod n)) mod n
例如：
(3-5) mod7
數學上可以將結果表示為與 5 同餘的非負餘數：
3-5 =-2 ≡ 5 mod7
因此，模 7 的結果可以表示為 5。
在實際程式中，要注意不同程式語言對負數 % 的定義可能與數學上的非負餘數不同。Java 的 % 是餘數運算，結果可能為負數；如果需要標準化為非負餘數，可以使用 Math.floorMod()。
System.out.println(-2 % 7); // -2
System.out.println(Math.floorMod(-2, 7)); // 5
(ax b) mod n = ((a mod n)x(b mod n)) mod n
例如：
(12x13) mod7
直接計算：
156 mod7=2
先取模也一樣：
(5x6) mod7
=30 mod7
=2
這代表我們不一定需要先算出完整的大數乘積，才進行取模。
對大型整數演算法來說，這是非常重要的特性。
模指數運算（Modular Exponentiation）是非對稱密碼學中極為常見的操作：
(a^b) mod n = ((a mod n)^b) mod n
例如：
10^4 mod7
先計算：
10^4=10000
再取模：
10000 mod7 = 4
先取模也一樣：
(10 mod 7)^4 mod7
=3^4 mod 7
=81 mod 7
=4
RSA 與 Diffie-Hellman 都會使用模指數運算。
但真實演算法中的數字通常大得多，直接先計算 a^b 再取模，可能產生極其龐大的中間結果。
因此，實際實作通常會使用**快速模冪（Fast Modular Exponentiation）**等演算法，在計算過程中持續取模，避免產生不必要的巨大數值。
我們先用 Java 示範基本的模加法、模乘法與模指數運算。
public class ModularArithmeticDemo {
public static void main(String[] args) {
int modulus = 7;
int addResult = (17 + 23) % modulus;
int multiplyResult = (12 * 13) % modulus;
int powerResult = modularPower(3, 4, modulus);
System.out.println("模加法結果：" + addResult);
System.out.println("模乘法結果：" + multiplyResult);
System.out.println("模指數結果：" + powerResult);
}
// 僅適用於本例中的小型非負整數
private static int modularPower(int base, int exponent, int modulus) {
int result = 1;
for (int i = 0; i < exponent; i++) {
result = (result * base) % modulus;
}
return result;
}
}
執行結果：
模加法結果：5
模乘法結果：2
模指數結果：4
這個範例是為了理解數學概念而設計的簡化版本。它使用迴圈逐次相乘，時間複雜度為 O(e)，其中 e 是指數。
對於 RSA 這種指數可能有數千個位元的情境，這種寫法並不適合直接使用。真實系統應使用經過驗證的密碼學函式庫，而不是自行實作完整的 RSA 或其他密碼演算法。
Java 的 int 與 long 都有固定範圍。當數字超出範圍時，就可能發生整數溢位。
而非對稱密碼學通常會使用非常大的整數，因此 Java 提供了 BigInteger 類別。
import java.math.BigInteger;
public class BigIntegerModDemo {
public static void main(String[] args) {
BigInteger base = BigInteger.valueOf(3);
BigInteger exponent = BigInteger.valueOf(4);
BigInteger modulus = BigInteger.valueOf(7);
BigInteger result =
base.modPow(exponent, modulus);
System.out.println("結果：" + result);
}
}
執行結果：
結果：4
關鍵方法是：
base.modPow(exponent, modulus);
它會計算：
base^{exponent} mod modulus
這比自行先計算完整的冪次，再取模，更適合大型整數運算。
不過，BigInteger 是通用的大整數工具，不能因此就假設所有操作都具有密碼學所需的側通道防護。在實際密碼學應用中，應優先使用 Java JCA/JCE 所提供的標準密碼學 API，避免直接以自行組合的數學運算取代經過驗證的密碼實作。
前面我們已經學會模加法、模乘法與模指數運算。
接下來要介紹一個在 RSA 中非常重要的概念：模反元素。
一般算術中，如果：
3x4=12
那麼我們可以利用除法，從 12 與 3 推回 4。
在模運算中，也存在類似的概念，但我們不能直接把一般除法搬過來使用。
我們需要的是模反元素。
假設模數為 n，如果存在整數 x，使得：
a * x ≡ 1 (mod n)
那麼 x 就稱為 a 在模 n 下的乘法反元素。
例如，求 3 在模 7 下的乘法反元素。
我們希望找到一個數 x，使得：
3x ≡ 1 mod7
逐一嘗試：
3x1=3
3x2=6
3x3=9 ≡2 mod7
3x4=12 ≡5 mod7
3x5=15 ≡1 mod7
因此：
3^{-1} ≡5 mod7
這裡的 3^{-1} 不是一般實數中的倒數 1/3，而是指模 7 下的乘法反元素。
驗證：
3x5=15 ≡1 mod7
不是每一個整數，在每一個模數下都有乘法反元素。
重要條件是：
gcd(a,n)=1
也就是 a 與 n 必須互質。
例如，3 在模 7 下有反元素，因為：
gcd(3,7)=1
但 2 在模 6 下沒有反元素，因為：
gcd(2,6)=2
我們無法找到整數 x，讓：
2x ≡ 1 (mod6)
原因是 2x 一定是偶數，不可能除以 6 後得到餘數 1。
這就是為什麼前面介紹的最大公因數與互質概念，會在這裡再次出現。
Java BigInteger 提供 modInverse() 方法。
import java.math.BigInteger;
public class ModularInverseDemo {
public static void main(String[] args) {
BigInteger a = BigInteger.valueOf(3);
BigInteger modulus = BigInteger.valueOf(7);
BigInteger inverse = a.modInverse(modulus);
System.out.println("模反元素：" + inverse);
System.out.println(
"驗證結果：" + a.multiply(inverse).mod(modulus)
);
}
}
執行結果：
模反元素：5
驗證結果：1
如果輸入的數字與模數不互質，modInverse() 就無法找到反元素，會拋出 ArithmeticException。
這個方法稍後會在理解 RSA 金鑰產生時派上用場。
到目前為止，我們已經認識了：
這些概念並不是互不相關的數學知識，而是會組合起來，形成非對稱密碼學的數學基礎。
以 RSA 為例，金鑰產生的概念可以先簡化理解如下。
選擇兩個不同的大質數：
p,q
然後計算：
n=pq
這個 n 會成為 RSA 公開金鑰與私密金鑰的重要參數。
當 p 與 q 是不同質數時，RSA 會使用：
φ(n)=(p-1)(q-1)
其中 φ 是 Euler's totient function（歐拉函數）。
它表示在 1 到 n 之間，與 n 互質的正整數數量。
選擇公開指數 e，使其符合：
1 <e <φ(n)
且：
gcd(e,φ(n))=1
這個互質條件，確保 e 在模 φ(n) 下存在乘法反元素。
接著，求出 d，使得：
ed ≡1 mod{φ(n)}
也就是：
d ≡ e^{-1} mod{φ(n)}
這裡的 d，就是 RSA 私密金鑰的重要部分。
你會發現，今天介紹的模反元素，直接出現在 RSA 的金鑰產生過程中。
而模指數運算也會出現在 RSA 的核心運算中。概念上，RSA 的基本關係可以寫成：
c ≡ m^e mod n
以及：
m ≡ c^d mod n
其中 m 是經過適當編碼的訊息代表值，c 是運算結果。這裡的公式是用來理解數學關係的簡化表示；實際 RSA 加密必須搭配安全的填補機制，例如 RSA-OAEP，而數位簽章則應使用適當的簽章方案，例如 RSA-PSS。
這些公式背後的完整數學推導，以及 RSA 在實際系統中的正確使用方式，我們會在後續文章逐步展開。
今天我們先不急著實作完整的非對稱加密演算法，而是建立後續文章會反覆使用的數學基礎。
| 概念 | 意義 | 後續應用 |
|---|---|---|
| 質數 | 只有 1 與本身兩個正因數的整數 | RSA 金鑰產生 |
| 最大公因數 | 兩個整數最大的共同因數 | 判斷是否互質 |
| 互質 | 最大公因數為 1 | 模反元素存在條件 |
| 模運算 | 以除法餘數進行運算 | RSA、Diffie-Hellman |
| 模指數 | 計算a^b mod n | RSA、Diffie-Hellman |
| 模反元素 | 找出乘積同餘於 1 的整數 | RSA 私密指數產生 |
如果只記得今天最重要的三件事，我建議記住：
下一篇，我們會繼續深入數論，介紹歐幾里得演算法與擴展歐幾里得演算法，學習如何有效率地求出最大公因數與模反元素。
當我們能真正理解這些數學工具，就能看懂 RSA 如何產生金鑰，也能更有系統地理解非對稱密碼學的設計原理。
密碼學不只是把資料加密，而是將數學結構轉化為可以實際運作的安全機制。
iThome鐵人賽
看影片追技術